#include <iostream>
#include <memory>
#include <vector>
#include <sstream>
#include <string>
#include <windows.h>
using namespace std;

// 抽象表达式类
class Expression
{
public:
    virtual int interpret() = 0; // 解释方法
    virtual ~Expression() = default;
};

// 数字类（终结符表达式）
class Number : public Expression
{
private:
    int number;

public:
    explicit Number(int num) : number(num) {}
    int interpret() override
    {
        return number;
    }
};

// 加法类（非终结符表达式）
class Add : public Expression
{
private:
    shared_ptr<Expression> left, right;

public:
    Add(shared_ptr<Expression> left, shared_ptr<Expression> right) : left(left), right(right) {}
    int interpret() override
    {
        return left->interpret() + right->interpret();
    }
};

// 减法类（非终结符表达式）
class Subtract : public Expression
{
private:
    shared_ptr<Expression> left, right;

public:
    Subtract(shared_ptr<Expression> left, shared_ptr<Expression> right) : left(left), right(right) {}
    int interpret() override
    {
        return left->interpret() - right->interpret();
    }
};

// 乘法类（非终结符表达式）
class Multiply : public Expression
{
private:
    shared_ptr<Expression> left, right;

public:
    Multiply(shared_ptr<Expression> left, shared_ptr<Expression> right) : left(left), right(right) {}
    int interpret() override
    {
        return left->interpret() * right->interpret();
    }
};

// 解析器类（上下文）
class ExpressionParser
{
public:
    shared_ptr<Expression> parse(const string &expression)
    {
        vector<shared_ptr<Expression>> numbers;
        stringstream ss(expression);
        string token;

        // 使用空格分割表达式
        while (getline(ss, token, ' '))
        {
            if (token == "+")
            {
                shared_ptr<Expression> right = numbers.back();
                numbers.pop_back();
                shared_ptr<Expression> left = numbers.back();
                numbers.pop_back();
                numbers.push_back(make_shared<Add>(left, right));
            }
            else if (token == "-")
            {
                shared_ptr<Expression> right = numbers.back();
                numbers.pop_back();
                shared_ptr<Expression> left = numbers.back();
                numbers.pop_back();
                numbers.push_back(make_shared<Subtract>(left, right));
            }
            else if (token == "*")
            {
                shared_ptr<Expression> right = numbers.back();
                numbers.pop_back();
                shared_ptr<Expression> left = numbers.back();
                numbers.pop_back();
                numbers.push_back(make_shared<Multiply>(left, right));
            }
            else
            {
                numbers.push_back(make_shared<Number>(stoi(token)));
            }
        }

        return numbers.back();
    }
};

// 客户端
int main()
{
    SetConsoleOutputCP(65001);
    string expression = "3 5 2 * + 8 -"; // 后缀表达式：3 + (5 * 2) - 8
    ExpressionParser parser;

    shared_ptr<Expression> exp = parser.parse(expression);
    cout << "结果：" << exp->interpret() << endl; // 输出结果

    return 0;
}
